mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, especially

order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...

, a prefix ordered set generalizes the intuitive concept of a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

by introducing the possibility of continuous progress and continuous branching. Natural prefix orders often occur when considering

dynamical systems In mathematics, a dynamical system is a system in which a Function (mathematics), function describes the time dependence of a Point (geometry), point in an ambient space, such as in a parametric curve. Examples include the mathematical models ...

as a set of functions from ''time'' (a totally-ordered set) to some

phase space The phase space of a physical system is the set of all possible physical states of the system when described by a given parameterization. Each possible state corresponds uniquely to a point in the phase space. For mechanical systems, the p ...

. In this case, the elements of the set are usually referred to as ''executions'' of the system. The name ''prefix order'' stems from the prefix order on words, which is a special kind of

substring In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequenc ...

relation and, because of its discrete character, a tree.

Formal definition

A prefix order is a

binary relation In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...

"≤" over a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

''P'' which is antisymmetric, transitive, reflexive, and downward total, i.e., for all ''a'', ''b'', and ''c'' in ''P'', we have that: *''a ≤ a'' (reflexivity); *if ''a ≤ b'' and ''b ≤ a'' then ''a'' = ''b'' (antisymmetry); *if ''a ≤ b'' and ''b ≤ c'' then ''a ≤ c'' (transitivity); *if ''a ≤ c'' and ''b ≤ c'' then ''a ≤ b'' or ''b ≤ a'' (downward totality).

Functions between prefix orders

While between partial orders it is usual to consider order-preserving functions, the most important type of functions between prefix orders are so-called history preserving functions. Given a prefix ordered set ''P'', a history of a point ''p''∈''P'' is the (by definition totally ordered) set ''p''− = . A function ''f'': ''P'' → ''Q'' between prefix orders ''P'' and ''Q'' is then history preserving if and only if for every ''p''∈''P'' we find ''f''(''p''−) = ''f''(''p'')−. Similarly, a future of a point ''p''∈''P'' is the (prefix ordered) set ''p''+ = and ''f'' is future preserving if for all ''p''∈''P'' we find ''f''(''p''+) = ''f''(''p'')+. Every history preserving function and every future preserving function is also order preserving, but not vice versa. In the theory of dynamical systems, history preserving maps capture the intuition that the behavior in one system is a ''refinement'' of the behavior in another. Furthermore, functions that are history and future preserving surjections capture the notion of bisimulation between systems, and thus the intuition that a given refinement is ''correct'' with respect to a specification. The

range Range may refer to: Geography * Range (geographic), a chain of hills or mountains; a somewhat linear, complex mountainous or hilly area (cordillera, sierra) ** Mountain range, a group of mountains bordered by lowlands * Range, a term used to i ...

of a history preserving function is always a prefix closed subset, where a subset ''S ⊆ P'' is prefix closed if for all ''s,t ∈ P'' with ''t∈S'' and ''s≤t'' we find ''s∈S''.

Product and union

Taking history preserving maps as ''morphisms'' in the

category Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * Category ( ...

of prefix orders leads to a notion of product that is ''not'' the Cartesian product of the two orders since the Cartesian product is not always a prefix order. Instead, it leads to an ''arbitrary interleaving'' of the original prefix orders. The union of two prefix orders is the

disjoint union In mathematics, the disjoint union (or discriminated union) A \sqcup B of the sets and is the set formed from the elements of and labelled (indexed) with the name of the set from which they come. So, an element belonging to both and appe ...

, as it is with partial orders.

Isomorphism

Any bijective history preserving function is an

order isomorphism In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be co ...

. Furthermore, if for a given prefix ordered set ''P'' we construct the set ''P- ≜ '' we find that this set is prefix ordered by the subset relation ⊆, and furthermore, that the function ''max: P- → P'' is an isomorphism, where ''max(S)'' returns for each set ''S∈P-'' the maximum element in terms of the order on P (i.e. ''max(p-) ≜ p'').

References

* * * {{Order theory Dynamical systems Order theory Trees (data structures)